package com.cy.letcode.link.合并k个升序链表;

/**
 *
 */
class 分治法Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSubList(lists, 0, lists.length - 1);
    }

    public ListNode mergeSubList(ListNode[] lists, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return lists[start];
        }
        int mid = (start + end) >> 1;
        return mergeTwo(mergeSubList(lists, start, mid), mergeSubList(lists, mid + 1, end));

    }

    public ListNode mergeTwo(ListNode l1, ListNode l2) {
        ListNode curr = new ListNode(-1);
        ListNode pre = curr;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                pre.next = new ListNode(l2.val);
                l2 = l2.next;
            } else {
                pre.next = new ListNode(l1.val);
                l1 = l1.next;
            }
            pre = pre.next;
        }
        pre.next = l1 == null ? l2 : l1;
        return curr.next;

    }
}